package com.zsj.heap;


/**
 * @Author zsj
 * @Version 1.0
 * @Date 2024/4/9 19:57
 * @Description 小顶堆
 */
public class MinHeap {
    int[] arr;
    int size;

    public MinHeap(int capacity) {
        this.arr = new int[capacity];
    }

    public MinHeap(int[] arr) {
        this.arr = arr;
        size = arr.length;
        //建堆
        heapify();
    }

    private void heapify() {
        //找到最后一个非叶子节点
        for (int i = size / 2 - 1; i >= 0; i--) {
            //从最后一个非叶子节点开始
            down(i);
        }
    }

    private void down(int parent) {
        // 下潜方法 比较两个哪个比较小
        //先算出两个孩子的位置
        int left = parent * 2 + 1;
        int right = left + 1;
        int min = parent;
        if (left < size && arr[min] > arr[left]) {
            //保证不越界的同时 父节点的值大于了左节点
            min = left;
        }
        //一样的道理不做解释
        if (right < size && arr[min] > arr[right]) {
            min = right;
        }
        //到这里说明交换完成
        if (parent != min) {
            swap(parent, min);//交换两个位置的值
            down(min);//继续下潜
        }
    }


    private void swap(int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public void replace(int replaced) {
        arr[0] = replaced;
        down(0);
    }

    /**
     * 堆尾部添加元素
     */
    public boolean offer(int value) {
        if (size >= arr.length) return false;
        arr[size++] = value;
        up(size - 1);
        return true;
    }

    private void up(int offered) {
        //已知子计算父的公式为 (son-1) /2
        int parent = (offered - 1) / 2;
        if (offered != 0 && arr[parent] > arr[offered]) {
            //如果父节点的值大于当前节点
            swap(parent, offered);//交换两个节点的值
            up(parent);//继续上浮
        }
    }

    public int poll() {
        if (size == 0) throw new RuntimeException("arr is empty");
        int ans = arr[0];
        swap(0, size-- - 1);
        down(0);
        return ans;
    }

    public int peek() {
        return arr[0];
    }

    public boolean isFull() {
        return size == arr.length;
    }

    public boolean isEmpty() {
        return size == 0;
    }

   /* public static void main(String[] args) {
        MinHeap minHeap = new MinHeap(10);
        //13257
//        System.out.println(Arrays.toString(minHeap.arr));
        minHeap.offer(1);
        minHeap.offer(0);
        minHeap.offer(5);
        minHeap.offer(6);
        minHeap.offer(2);
        minHeap.offer(3);
        minHeap.offer(8);
        System.out.println(Arrays.toString(minHeap.arr));//0136258
        minHeap.poll();
        System.out.println(Arrays.toString(minHeap.arr));//123685
    }*/


}
